MLSE (Maximum Likelihood Sequence Estimation) is a demodulation technique that also suppresses ISI (Inter-Symbol Interference) from a signal which is modulated in accordance with a particular constellation and transmitted over a channel. ISI causes the equalization complexity to increase as a power of the constellation size. Relatively large signal constellations such as 16-, 32- and 64-QAM (Quadrature Amplitude Modulation) have been adopted in EDGE (Enhanced Data Rates for GSM Evolution), HSPA (High Speed Packet Access), LTE (Long Term Evolution) and WiMax (Worldwide Interoperability for Microwave Access). In HSPA, multi-code transmission creates even larger effective constellations. Also, MIMO (Multiple-Input, Multiple-Output) schemes with two or more streams have been adopted in HSPA, LTE and WiMax. MIMO implementations also yield relatively large effective constellations. ISI causes equalization complexity to further increase when any of these techniques occur in combination, e.g. multi-code and MIMO.
In the ISI context, the ideal equalization scheme is MLSE, in the sense of maximizing the probability of correctly detecting the transmitted sequence of symbols, or sequences of symbols in the MIMO case. However, the complexity of MLSE increases substantially as a function of the size of the modulation constellation and/or because of the exponential effects of MIMO or multi-codes to the point where MLSE becomes impractical. Less complex solutions are available such as, DFSE (Decision-Feedback Sequence Estimation), DFE (Decision-Feedback Equalization), etc. Each of these solutions attempts to strike a balance between accuracy and complexity.
For a symbol-spaced channel model with memory M in a MIMO environment, the system model is given by:rk=HMsk-M+ . . . +H1sk-1+H0sk+Vk  (1)Here the element Hm, i, j of Hm describes the channel from transmit antenna j to receive antenna i at a delay of m symbols. The channel matrices are assumed to be constant over the duration of a burst of data, which will be equalized in one shot. The signal sk has symbol constellation Q of size q. The noise vk is white and Gaussian.
The general ISI scenario includes MIMO. Without much loss of generality, consider the case of a single transmitted signal. For a channel with memory M, MLSE operates on the standard highly regular ISI trellis with qM states, and qM+1 branches per stage. The storage complexity of MLSE is roughly driven by the number of states, and the computational complexity by the number of branches. As either M or q grows large, the complexity explodes. Stage k of the trellis describes the progression from state (ŝk-M . . . ŝk-1) to state (ŝk-M+1 . . . ŝk). The branch from (ŝk-M . . . ŝk-1) to (ŝk-M+1 . . . ŝk) represents the symbol ŝk. Note that for the ISI trellis, all branches ending in (ŝk-M+1 . . . ŝk) share the same symbol. For notational simplicity, the states at each stage are labeled 0 to qM−1. Each index represents a distinct value of (ŝk-M+1 . . . ŝk). A branch is labeled by its starting and ending state pair (j′,j). For each state j, the fan-in I(j) and the fan-out O(j) are the set of incoming and outgoing branches, respectively. For the ISI trellis, all fan-in and fan-out sets have the same size q.
The branch metric of a branch (j′,j) at step k in the MLSE trellis is given by:ek(j′,j)=|rk−HMŝk-M+ . . . +H0ŝk|2  (2)Without much loss of generality, the trellis is assumed to start at time 0 in state 0. The state metric computation proceeds forward from there. At time k, the state, or cumulative, metric Ek(j) of state j is given in terms of the state metrics at time k−1, and the branch metrics at time k is given by:
                                          E            k                    ⁡                      (            j            )                          =                              min                                          j                ′                            ∈                              I                ⁡                                  (                  j                  )                                                              ⁢                      (                                                            E                                      k                    -                    1                                                  ⁡                                  (                                      j                    ′                                    )                                            +                                                e                  k                                ⁡                                  (                                                            j                      ′                                        ,                    j                                    )                                                      )                                              (        3        )            In addition, the state in I(j) that achieves the minimum is the so-called predecessor of state j, and denoted πk-1(j). Also, the oldest symbol ŝk-M in the corresponding M-tuple (ŝk-M, . . . , ŝk-1) is the tentative symbol decision looking back from state j at time k. It is possible to trace back a sequence over the different states to time 0, by following the chain πk-1(j), πk-2(πk-1(j)), etc. The corresponding symbols ŝk-M, ŝk-M−1, etc, are the tentative decisions of MLSE looking back from state j at time k. In general, looking back from different states at time k, the decisions tend to agree more the older the symbols. That is, the longer the delay for a decision, the better. Typically, there is a chosen delay D, and the final decision about symbol ŝk-M-D is made by tracing back from the state (ŝk-M+1 . . . ŝk) with the smallest state metric. We note again, however, that MLSE has exploding complexity, whether due to the size of the modulation itself, or to the exponential effect of ISI.
Another conventional equalization technique is MSA (Multi-Stage Arbitration). MSA involves sifting through a large set of candidates in multiple stages, where each stage rejects some candidates until a single candidate is left after the final stage. One specific example of MSA is generalized MLSE arbitration where the first stage is a linear equalizer. The second stage implements MLSE based on a sparse irregular trellis over a reduced state space. Iterative Tree Search (ITS) has also been used for performing equalization in MIMO QAM environments. ITS exploits the triangular factorization of the channel. In addition, ITS uses the M-algorithm for reducing the search for the best candidate. ITS breaks down the search further, by dividing the QAM constellation in its four quadrants, and representing each quadrant by its centroid in intermediate computations. The selected quadrant itself is subdivided again into its 4 quadrants, and so on. This results in a quaternary tree search. Other conventional approaches give particular attention to the additional error introduced by the use of centroids instead of true symbols. The error is modeled as Gaussian noise whose variance is determined and incorporated in likelihood computations. However, a tight connection is typically made between the centroid representation and the bit mapping from bits to symbols. That is, if a so-called multi-level bit mapping is employed, then identifying a quadrant is equivalent to making a decision on a certain pair of bits. Such constraints place a restriction on bit mappings, restricting the design of subsets.